package ljl.codetop300;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 * 输入: candidates = [10,1,2,7,6,1,5], target = 8,
 * 输出:
 * [
 * [1,1,6],
 * [1,2,5],
 * [1,7],
 * [2,6]
 * ]
 * 示例 2:
 * <p>
 * 输入: candidates = [2,5,2,1,2], target = 5,
 * 输出:
 * [
 * [1,2,2],
 * [5]
 * ]
 * <p>
 * 感觉上就是一个普通的回溯
 * <p>
 * 逼逼半天不会做妈的
 */
public class _40_combination_sum_2 {

  /**
   * 这个官方题解真是剑走偏锋，很罕见的解法
   */
  static class off {
    List<int[]> freq = new ArrayList<>();
    List<List<Integer>> ans = new ArrayList<>();
    List<Integer> sequence = new ArrayList<>();

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
      Arrays.sort(candidates);
      for (int num : candidates) {
        int size = freq.size();
        if (freq.isEmpty() || num != freq.get(size - 1)[0]) {
          freq.add(new int[]{num, 1});
        } else {
          freq.get(size - 1)[1]++;
        }
      }
      dfs(0, target);
      return ans;
    }

    public void dfs(int pos, int rest) {
      if (rest == 0) {
        ans.add(new ArrayList<>(sequence));
        return;
      }
      if (pos == freq.size() || rest < freq.get(pos)[0]) {
        return;
      }

      dfs(pos + 1, rest);

      int most = Math.min(rest / freq.get(pos)[0], freq.get(pos)[1]);
      for (int i = 1; i <= most; ++i) {
        sequence.add(freq.get(pos)[0]);
        dfs(pos + 1, rest - i * freq.get(pos)[0]);
      }
      for (int i = 1; i <= most; ++i) {
        sequence.remove(sequence.size() - 1);
      }
    }
  }

  /**
   * 他这个解法虽然很邪门，还挺快的
   */
  static class copy_off {

    public static void main(String[] args) {
      new copy_off().combinationSum2(new int[]{2, 5, 2, 1, 2}, 5);
    }

    List<int[]> freq = new ArrayList<>();
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> buf = new ArrayList<>();

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
      Arrays.sort(candidates);
      for (int i = 0; i < candidates.length; i++) {
        if (i > 0 && candidates[i] == candidates[i - 1]) {
          freq.get(freq.size() - 1)[1]++;
        } else {
          freq.add(new int[]{candidates[i], 1});
        }
      }
      dfs(0, target);
      return res;
    }

    void dfs(int pos, int rest) {
      if (rest == 0) {
        res.add(new ArrayList<>(buf));
      }
      if (pos == freq.size() || rest < freq.get(pos)[0]) return;

      dfs(pos + 1, rest);

      int[] pair = freq.get(pos);
      int times = Math.min(rest / pair[0], pair[1]);
      for (int i = 1; i <= times; i++) {
        buf.add(pair[0]);
        dfs(pos + 1, rest - i * pair[0]);
      }
      for (int i = 1; i <= times; i++) {
        buf.remove(buf.size() - 1);
      }
    }
  }

  // 标记数组
  static class Carl_v1 {
    LinkedList<Integer> path = new LinkedList<>();
    List<List<Integer>> ans = new ArrayList<>();
    boolean[] used;

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
      used = new boolean[candidates.length];
      Arrays.fill(used, false);
      Arrays.sort(candidates);
      backTracking(candidates, target, 0);
      return ans;
    }

    private void backTracking(int[] candidates, int rest, int startIndex) {
      if (rest == 0) {
        ans.add(new ArrayList<>(path));
      }
      for (int i = startIndex; i < candidates.length && rest >= candidates[i]; i++) {
        // 这 i > 0 改成 i > startIndex 直接可以省掉 used
        if (i > 0 && candidates[i] == candidates[i - 1] && !used[i - 1]) {
          continue;
        }
        used[i] = true;
        path.add(candidates[i]);
        backTracking(candidates, rest - candidates[i], i + 1);
        used[i] = false;
        path.removeLast();
      }
    }
  }

  /**
   * 这个解法比较完美，官方题解有点扯淡了
   */
  static class Carl_v2 {
    List<List<Integer>> res = new ArrayList<>();
    LinkedList<Integer> path = new LinkedList<>();

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
      Arrays.sort(candidates);
      backTracking(candidates, target, 0);
      return res;
    }

    private void backTracking(int[] candidates, int rest, int start) {
      if (rest == 0) {
        res.add(new ArrayList<>(path));
        return;
      }
      // 一开始不理解为什么 2 2 2 取了第一个还能取后面的？后来才知道，
      // 下一次是从下一个开始，而第一个肯定会被放进去
      for (int i = start; i < candidates.length && rest >= candidates[i]; i++) {
        if (i > start && candidates[i] == candidates[i - 1]) {
          continue;
        }
        path.add(candidates[i]);
        backTracking(candidates, rest - candidates[i], i + 1);
        path.removeLast();
      }
    }
  }

  /**
   * 易错点还是有几处的
   */
  static class copy_Carl_v2 {
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> buf = new ArrayList<>();
    int[] candidates;
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
      Arrays.sort(candidates);
      this.candidates = candidates;
      dfs(target, 0);
      return res;
    }
    void dfs(int rest, int pos) {
      if (rest == 0) {
        res.add(new ArrayList<>(buf));
        return;
      }
      for (int i = pos; i < candidates.length && rest >= candidates[i]; i++) {
        if (i > pos && candidates[i] == candidates[i - 1]) continue;
        buf.add(candidates[i]);
        dfs(rest - candidates[i], i + 1);
        buf.remove(buf.size() - 1);
      }
    }
  }
}